using System;
using System.Collections.Generic;
using System.Text;
//using AlgorithmsVisualized.Controls;
using GraphConstructor;
using AlgorithmsVisualized.Components;

namespace PrimDemo1
{
    /// <summary>
    /// Prim algorithm loops on every node, then trys to relax this node by updating its neighabours (if applicable)
    /// <complexty>
    /// Prim runs in v.lg(E)
    /// </complexty>
    /// </summary>
    [VisualAlgorithm]
    public class Prim : IGraph
    {
        internal class PrimEnumerated : IEnumerator<IStep>
        {
            SortedDictionary<Node, Node> Q;
            Prim g;
            Node n;
            IStep step;
            int i;

            public IStep Current
            {
                get { return step; }
            }

            public void Dispose()
            {
                
            }

            object System.Collections.IEnumerator.Current
            {
                get { return step; }
            }

            public bool MoveNext()
            {
				if (Q == null || Q.Count == 0)
					return false;
				if (i >= n.Adj.Count)
				{
                    foreach (Node Key in Q.Keys)
                    {
                        n = Key;
                        break;
                    }

					Q.Remove(n);
					i = 0;
				}
				if (n.Adj.Count <= 0)
					return true;
				Edge d = n.Adj[i];
				if (d.NodeTo.Value > d.Weight)
				{
                    if (d.NodeTo.Parent != null)
                        step.State.Edges.Remove(new Edge(d.NodeTo.Parent.ID + d.NodeTo.ID, 0));
					Q.Remove(d.NodeTo);
                    //step.State.Edges.Remove(new Edge(d.NodeTo.ID + n.ID, 0));
					d.NodeTo.Parent = n;
                    d.NodeTo.Value = d.Weight;

                    Q.Add(d.NodeTo, null);
                    step.State.Edges.Add(d);

                    //step.State.Nodes.Add(d.NodeTo);
                    //step.State.Edges.Add(d);
				}
				i++;
				return true;
			}
            public void Reset()
            {
                step = new PrimStep();
                step.State = new Prim();
                foreach (Node n in g.Nodes)
                {
                    n.Value = int.MaxValue;
                    n.Parent = null;
                }
                if (g.StartNodes.Count == 0)
                    return;
                g.StartNodes[0].Value = 0;
                Q = new SortedDictionary<Node, Node>();
                foreach (Node n in g.Nodes)
                {
                    step.State.Nodes.Add(n);
                    Q.Add(n, null);
                }
                /*
                foreach (Edge edge in g.Edges)
                {
                    step.State.Edges.Add(edge);
                }*/
                foreach (Node Key in Q.Keys)
                {
                    n = Key;
                    break;
                }

                Q.Remove(this.n);
                i = 0;
            }

            public PrimEnumerated(Prim d)
            {
                g = d;
            }
        }
        internal class PrimStep : IStep
        {
            private bool _isFinal;
            private IGraph _state;

            public IGraph State
            {
                get { return _state; }
                set { _state = value; }
            }
            public bool IsFinal
            {
                get { return _isFinal; }
                set { _isFinal = value; }
            }
        }
        private List<Edge> _edges = new List<Edge>();
        private List<Node> _nodes = new List<Node>();
        private List<Node> _startNodes = new List<Node>();

        #region IGraph Members

        public bool IsWeighted
        {
            get
            {
                return true;
            }
            set
            {
            }
        }

        public bool IsDirected
        {
            get
            {
                return true;
            }
            set
            {
            }
        }

        public List<Edge> Edges
        {
            get { return _edges; }
            set { _edges = value; }
        }
        public List<Node> Nodes
        {
            get { return _nodes; }
            set { _nodes = value; }
        }
        public List<Node> StartNodes
        {
            get
            {
                return _startNodes;
            }
            set
            {
                _startNodes = value;
            }
        }
        #endregion

        public IEnumerator<IStep> GetEnumerator()
        {
            return new PrimEnumerated(this);
        }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            throw new Exception("The method or operation is not implemented.");
        }

        #region IGraph Members

        public string Name
        {
            get
            {
                return "Prim";
            }
        }
        public string Description
        {
            get
            {
                return "Prim algorithm loops on every node, then trys to relax this node by updating its neighabours (if applicable)";
            }
        }
        public string Complexty
        {
            get
            {
                return "v.lgE";
            }
        }

        #endregion
    }
}
